package binarytree

import (
	"fmt"
	"strconv"
	"strings"
)


type TreeNode struct{
	Val int
	Left,Right *TreeNode
}

// 二叉树的所有路径
func binaryTreePaths(root *TreeNode) []string {
	// 搜索路径  dfs
	var res []string
	var path []int
	if root == nil {return res}
	traversal(root, &path, &res)
	return  res
}

// 递归的方式  前序遍历
func traversal(root *TreeNode, path *[]int, res *[]string) {
	*path = append(*path, root.Val)
    //确定终止条件  
	if root.Left==nil && root.Right==nil {
		// 终止处理  找到一条路径
		// 当前节点需要加入
		// *path = append(*path, root.Val)
		// 构建string类型的路径
		var s strings.Builder
		for i:=0;i<len(*path);i++{
			ss := fmt.Sprintf("%d->",(*path)[i])
			s.WriteString(ss)
		}
		// 去除最后一个 ->
		*res = append(*res, s.String()[:s.Len()-2])
	}
	// 进入单层处理逻辑
	// 前序遍历  先处理中间节点 即路径上的节点
	
	// 左
	if root.Left!=nil {
		traversal(root.Left, path,res)
		// 回溯  有一个递归就有一个回溯
		*path = (*path)[:len(*path)-1]  // 弹出
	}
	// 右
	if root.Right!=nil {
		traversal(root.Right,path,res)
		// 回溯  有一个递归就有一个回溯
		*path = (*path)[:len(*path)-1]  // 弹出
	}
}

// 使用迭代方式的前序遍历方法
func binaryTreePathsNon(root *TreeNode)[]string{
	stack := []*TreeNode{}
	paths := make([]string, 0)
	res := make([]string, 0)
	if root != nil {
		stack = append(stack, root)
		paths = append(paths, "")
	}
	for len(stack) > 0 {
		l := len(stack)
		node := stack[l-1]
		path := paths[l-1]
		stack = stack[:l-1]
		paths = paths[:l-1]
		if node.Left == nil && node.Right == nil {
			res = append(res, path+strconv.Itoa(node.Val))
			continue
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
			paths = append(paths, path+strconv.Itoa(node.Val)+"->")
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
			paths = append(paths, path+strconv.Itoa(node.Val)+"->")
		}
	}
	return res
}